package longestPalindrome;

import org.junit.Test;

/**
 * @Auther: wdd
 * @Date: 2019/9/15 11:10
 * @Description:
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 *
 * 示例 2：
 * 输入: "cbbd"
 * 输出: "bb"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    @Test
    public void test(){
        String s = "abbac";
        String s1 = longestPalindrome(s);
        System.out.println(s1);
    }

    public String longestPalindrome(String s) {
        String res = "";
        for(int i=0; i<s.length(); i++){
            // aba 形式
            int right = i, left = i;
            while (left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            String cur = s.substring(left+1,right);
            if(cur.length() > res.length()){
                res = cur;
            }

            // abba 形式
            right = i+1;
            left = i;
            while (left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            cur = s.substring(left+1,right);
            if(cur.length() > res.length()){
                res = cur;
            }
        }
        return res;
    }

}
